package william.heap;

import java.util.PriorityQueue;

/**
 * @author ZhangShenao
 * @date 2024/2/20
 * @description <a href="https://leetcode.cn/problems/kth-largest-element-in-a-stream/">...</a>
 */
public class Leetcode703_数据流中第K大元素 {
    class KthLargest {
        /**
         * 维护一个小根堆
         */
        private PriorityQueue<Integer> heap;

        /**
         * 堆的最大容量
         */
        private int k;

        /**
         * 构造器
         */
        public KthLargest(int k, int[] nums) {
            this.heap = new PriorityQueue<>();
            this.k = k;

            //初始化元素
            for (int i = 0; i < nums.length; i++) {
                add(nums[i]);
            }
        }

        public int add(int val) {
            if (heap.size() < k) {  //堆中元素不满k个,直接插入
                heap.offer(val);
            } else if (val > heap.peek()) {//当前元素大于堆顶元素,将堆顶元素弹出,将当前元素插入
                heap.poll();
                heap.offer(val);
            }   //当前元素比堆顶元素小,直接忽略

            //返回堆顶元素
            return heap.peek();
        }
    }
}
